/*
 * @lc app=leetcode.cn id=1202 lang=java
 *
 * [1202] 交换字符串中的元素
 */

// @lc code=start
class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        DisjointSetUnion dsu = new DisjointSetUnion(s.length());
        for (List<Integer> pair : pairs) {
            dsu.unionSet(pair.get(0), pair.get(1));
        }
        Map<Integer, List<Character>> map = new HashMap<Integer, List<Character>>();
        for (int i = 0; i < s.length(); i++) {
            int parent = dsu.find(i);
            if (!map.containsKey(parent)) {
                map.put(parent, new ArrayList<Character>());
            }
            map.get(parent).add(s.charAt(i));
        }
        for (Map.Entry<Integer, List<Character>> entry : map.entrySet()) {
            Collections.sort(entry.getValue(), new Comparator<Character>() {
                public int compare(Character c1, Character c2) {
                    return c2 - c1;
                }
            });
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            int x = dsu.find(i);
            List<Character> list = map.get(x);
            sb.append(list.remove(list.size() - 1));
        }
        return sb.toString();
    }
}

class DisjointSetUnion {
    int[] father;
    int[] weight;//节点数目
    int count;//代表数量

    public DisjointSetUnion(int n) {
        this.count = n;
        weight = new int[n];
        Arrays.fill(rank, 1);//节点数目全改为1
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;//父节点先指向自己
        }
    }

    public int find(int x) {
        return father[x] == x ? x : (father[x] = find(father[x]));//这么写倒是省代码。
    }

    public void unionSet(int x, int y) {//合并操作，不需要返回判断是否为连通分量
        int fx = find(x), fy = find(y);
        if (fx == fy) {//两者的父节点相同，证明在一个连通分量内，不需要进行合并操作
            return;
        }
        if (weight[fx] < weight[fy]) {//看那方节点多,多的那个变成fx
            int temp = fx;
            fx = fy;
            fy = temp;
        }
        //因为显然把节点少的并到节点多的分量里比较省时间。
        weight[fx] += weight[fy];
        f[fy] = fx;
    }
}
// @lc code=end

